package linkedList;

/**
 * 反转链表 -206
 *
 * @author yyz
 * @create 2023-11-12 16:26
 */
public class 反转链表 {
    /**
     * 反转单链表（方法1）
     *
     * @param head 原链表头节点
     * @return 反转后的链表头节点
     */
    public static ListNode reverseList(ListNode head) {
        // 如果链表为空或只有一个节点，则直接返回头节点本身
        if (head == null || head.next == null) {
            return head;
        }
        // 递归反转链表，并得到反转后的头节点newHead
        ListNode newHead = reverseList(head.next);
        // 将当前节点head的下一个节点的next指针指向head，实现链表的反转
        head.next.next = head;
        // 将当前节点head的next指针置为null，防止出现环形链表
        head.next = null;
        // 返回反转后的链表头节点newHead
        return newHead;
    }


    /**
     * 反转单链表(方法2)
     *
     * @param o1 原链表头节点
     * @return 反转后的链表头节点
     */
    public static ListNode reverseList2(ListNode o1) {
        // 定义一个节点n1，表示新链表的头节点，初始值为null
        ListNode n1 = null;
        // 定义一个指针p，指向原链表的头节点o1
        ListNode p = o1;
        // 遍历原链表，将每个节点插入到n1所代表的新链表的头部
        while (p != null) {
            // 创建一个新节点，其val为p节点的val，next为n1
            // 这样就实现了将p节点插入到n1所代表的新链表的头部
            n1 = new ListNode(p.val, n1);
            // 将指针p指向原链表中的下一个节点，继续遍历
            p = p.next;
        }
        // 返回新链表的头节点n1
        return n1;
    }

    /**
     * 反转单链表(方法3)
     *
     * @param head 原链表头节点
     * @return 反转后的链表头节点
     */
    public static ListNode reverseList3(ListNode head) {
        // 如果链表为空或者只有一个节点，直接返回o1
        if (head == null || head.next == null) {
            return head;
        }
        // 定义两个节点pre和curr，分别表示前驱节点和当前节点，初始值分别为null和head
        ListNode pre = null;
        ListNode curr = head;
        // 遍历原链表，反转每个节点的next指针
        while (curr != null) {
            // 定义一个节点next，表示当前节点curr的下一个节点
            ListNode next = curr.next;
            // 将当前节点curr的next指针指向其前驱节点pre
            curr.next = pre;
            // 更新pre和curr的值，继续向后遍历
            pre = curr;
            curr = next;
        }

        // 返回反转后的链表头节点pre
        return pre;
    }

    /**
     * 反转单链表(方法4)
     *
     * @param o1 原链表头节点
     * @return 反转后的链表头节点
     */
    public static ListNode reverseList4(ListNode o1) {
        // 如果链表为空或者只有一个节点，直接返回o1
        if (o1 == null || o1.next == null) {
            return o1;
        }
        // 定义节点n1指向o1，节点o2指向o1的下一个节点
        ListNode n1 = o1;
        ListNode o2 = o1.next;
        // 遍历链表进行反转
        while (o1.next != null) {
            // 将o1的next指针指向o2的next
            o1.next = o2.next;
            // 将o2的next指针指向n1，完成局部反转
            o2.next = n1;
            // 更新n1和o2的值，准备下一轮反转
            n1 = o2;
            o2 = o1.next;
        }
        // 返回反转后的链表头节点n1
        return n1;
    }


    public static void main(String[] args) {
        ListNode list = ListNode.of(1, 2, 3, 4, 5);

        System.out.println(reverseList(list));
    }
}
